Linked List Random Node || Random Pick Index

发表于

Linked List Random Node

Question

Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.

Follow up:
What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

1
2
3
4
5
6
7
// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();
Analysis

朴素做法是遍历数组得到len后，根据len生成随机数从中任取一个，即每个节点被选择的概率都相同。但是follow up中提示链表的长度未知，可能很长，所以利用水塘抽样即可在遍历的同时以均等的概率选取节点。

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    public Solution(ListNode head) {
            this.head=head;
            this.rand=new Random();
        }
    
    /** Returns a random node's value. */
    public int getRandom() {
        int i=2;
        int res=head.val;
        ListNode p=head.next;
        while(p!=null){
            if(rand.nextInt(i)==0)
                res=p.val;
            i++;
            p=p.next;
        }
        return res;
    }
    
    private ListNode head;
    private Random rand;
}
/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */

Random Pick Index

Question

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

1
2
3
4
5
6
int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);
// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);
// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);
Analysis
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Solution {
    public Solution(int[] nums) {
        this.rand=new Random();
        this.number=nums;
    }
    
    public int pick(int target) {
        int i=1;
        int count=2;
        int res=0;
        boolean flag=true;
        while(i<number.length){
            if(number[i]==target&&flag){
                res=i;
                flag=false;
            }
            else if(number[i]==target){
                if(rand.nextInt(count)==0)
                    res=i;
                count++;
            }
            i++;
        }
        return res;
    }
    
    private Random rand;
    int[] number;
}
/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);
 */